// hdu3715
// 题意：给定n(<=200)，m(<=10000)，现在有m组数ai, bi, ci(0<=ai, bi<n,
//       0<=ci<=2)。现在给了一段程序
//        go(int dep, int n, int m)
//        begin
//        	output the value of dep
//        	if (dep < m && x[a[dep]] + x[b[dep]] != c[dep])
//        		go(dep + 1, n, m)
//        end
//       初始调用go(0, n, m)，问能打印出的dep的最大值是多少？
//
// 题解：首先二分深度dep，然后对于当前深度，我们用2-sat来判定，即对于
//       前dep个深度的条件都要满足，我们另i(0<=i<n)表示x[i]为1, 
//       i(n<=i<2*n)表示x[i]为0。然后如果
//        c[dep]==0, 那么a[dep] + n和b[dep] + n矛盾;
//        c[dep]==1，即a[dep]和b[dep]+n以及b[dep]和a[dep]+n矛盾;
//        c[dep]==2，即a[dep]和b[dep]矛盾。
//       然后tarjan判有没有i和i+n在同一个联通分量内，如果有就是false。
//
// run: $exec < bfdiff.in
#include <iostream>
#include <stack>
#include <cstring>

int const maxn = 407;
int const maxm = 200007;
int head[maxn], end_point[maxm], next[maxm];
int alloc = 2;
int a[maxm], b[maxm], c[maxm];
int n, m;

void add_edge(int u, int v)
{
	end_point[alloc] = v; next[alloc] = head[u]; head[u] = alloc++;
}

int low[maxn], dfn[maxn], color[maxn];
bool instack[maxn];
int tick, color_tick;
std::stack<int> stk;

void tarjan(int u)
{
	low[u] = dfn[u] = ++tick;
	stk.push(u);
	instack[u] = true;
	for (int p = head[u]; p; p = next[p]) {
		int v = end_point[p];
		if (!dfn[v]) {
			tarjan(v);
			low[u] = std::min(low[u], low[v]);
		} else if (instack[v])
			low[u] = std::min(low[u], dfn[v]);
	}
	if (low[u] == dfn[u]) {
		int t;
		color_tick++;
		do { t = stk.top(); stk.pop(); color[t] = color_tick; instack[t] = false; }
		while (t != u);
	}
}

bool judge(int mid)
{
	std::memset(head, 0, sizeof(head));
	alloc = 2;
	for (int i = 0; i < mid; i++) {
		int u = a[i], v = b[i], t = c[i];
		if (!t) {
			add_edge(u, n + v);
			add_edge(v, n + u);
		} else if (t == 1) {
			add_edge(u, v);
			add_edge(n + v, n + u);
			add_edge(n + u, n + v);
			add_edge(v, u);
		} else {
			add_edge(n + u, v);
			add_edge(n + v, u);
		}
	}
	std::memset(dfn, 0, sizeof(dfn));
	std::memset(instack, 0, sizeof(instack));
	while (!stk.empty()) stk.pop();
	tick = color_tick = 0;
	for (int i = 0; i < 2 * n; i++)
		if (!dfn[i]) tarjan(i);
	for (int i = 0; i < n; i++)
		if (color[i] == color[i + n]) return false;
	return true;
}

int main()
{
	std::ios::sync_with_stdio(false);
	int T; std::cin >> T;
	while (T--) {
		std::cin >> n >> m;
		for (int i = 0; i < m; i++)
			std::cin >> a[i] >> b[i] >> c[i];
		int l = 0, r = m;
		while (l + 1 < r) {
			int mid = (l + r) / 2;
			if (judge(mid)) l = mid;
			else r = mid;
		}
		if (judge(r)) l = r;
		std::cout << l << '\n';
	}
}

